#include <iostream>
#include <vector>

using namespace std;

// 99.61 %
class Solution
{
  public:
	int searchInsert(vector<int> &nums, int target)
	{
		int l = 0, r = nums.size() - 1;
		if (target < nums[l])
			return 0;
		if (target > nums[r])
			return r + 1;
		while (l <= r)
		{
			int mid = (l + r) / 2;
			if (nums[mid] == target)
				return mid;
			else if (target > nums[mid] && target < nums[mid + 1])
				return mid + 1;
			else if (target > nums[mid])
				l = mid + 1;
			else
				r = mid - 1;
		}
		return -1;
	}
};

int main()
{
	int arr[] = {1, 3};
	int n = sizeof(arr) / sizeof(arr[0]);
	vector<int> myVector(arr, arr + n);
	int t = 2;
	cout << Solution().searchInsert(myVector, t) << endl;
	return 0;
}
